package com.chapter1.basic;

import java.util.Arrays;

import org.junit.Test;

/** 
 * @ClassName: BinarySearch 
 * @Description:二分法查找
 * @author minjun minjun@bw30.com
 * @date 2015-2-11 下午4:53:46 
 *  
 */
public class BinarySearch {
	
	@Test
	public void test(){
		int [] array={1,3,5,6,4};
		int key=1;
		Arrays.sort(array);//快排NlgN
		System.out.println("数组："+Arrays.toString(array)+"的元素"+key+"所在索引位置为："+binarySearch(key,array));//二分法：lgN
	}

	/**
	 * 
	* @Title: binarySearch 
	* @Description: 二分法查找
	* @param     设定文件 
	* @return void    返回类型 
	* @throws
	 */
	public int binarySearch(int key,int[] array){
		int start=0;
		int end=array.length-1;
		while(start<=end){
			int mid=start+(end-start)/2;
			
			if(key>array[mid]){
				start=mid+1;
			}else if(key<array[mid]){
				end=mid-1;
			}else{
				return mid;
			}
		}
		
		return -1;
	}
	
	/**
	 * 
	* @Title: binarySearchRecursive 
	* @Description: 二分法查找递归实现 
	* @param @param key
	* @param @param array
	* @param @return    设定文件 
	* @return int    返回类型 
	* @throws
	 */
	public int binarySearchRecursive(int key,int[] array,int start,int end){
		if(start>end){
			return -1;
		}else{
			int mid=start+(end-start)/2;
			if(key>array[mid]){
				return binarySearchRecursive(key, array, mid+1, end);
			}else if(key<array[mid]){
				return binarySearchRecursive(key, array, start, mid-1);
			}else{
				return mid;
			}
			
		}
	}
}
